#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;

class LRUCache
{
public:
    LRUCache(int capacity)
        : _capacity(capacity)
    {
    }
    int get(int key)
    {
        if (!cache.count(key))
        {
            return -1;
        }
        auto node = cache[key];
        _order.splice(_order.end(),_order,node);
        return node->second;
    }
    void put(int key, int value)
    {
        if (!cache.count(key))
        {
            if (cache.size() == _capacity)
            {
                // 超过capacity，把最开始的数据拿走
                cache.erase(_order.front().first);
                _order.pop_front();
            }
               //！！在放入新的值的时候，将list的迭代器指针指向这个新的值，后续可以直接通过这个来修改list
               //可以省去遍历的麻烦O(n) -> O(1)
                _order.push_back({key, value});
                cache[key] = --_order.end();
        }
        else
        {
           auto node = cache[key];
           node -> second = value;
           _order.splice(_order.end(),_order,node);
        }
    }
    void print()
    {
        for (auto &elem : _order)
        {
            cout << "(" << elem.first << "," << elem.second << ")";
        }
        cout << endl;
    }

private:
    unordered_map<int,list<pair<int,int>>::iterator> cache;
    list<pair<int, int>> _order;
    int _capacity;
};
void test()
{
    LRUCache lc(2);
    lc.put(1, 1);
    lc.put(2, 2);
    int num = lc.get(1);
    lc.print();
    cout << num << endl;
    lc.put(3, 3);
    lc.print();
    num = lc.get(2);
    cout << num << endl;
    lc.put(4, 4);
    num = lc.get(1);
    cout << num << endl;
    num = lc.get(3);
    cout << num << endl;
}
int main()
{
    test();
    return 0;
}
